package breadth_first_search;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;


public class BreadthFirstSearch2D {
	
	private Maze2D maze2d;
	public int pathLength[][];
	private boolean isVisited2D[][];
	
	/*
	 * CONSTRUCTOR FOR INITIALIZING maze2d.
	 */
	public BreadthFirstSearch2D(Maze2D maze){
		maze2d=maze;
		int n=maze2d.n;
		pathLength=new int[n][n];
		isVisited2D=new boolean[n][n];
	}
	
	
	/*
	 * FUNCTION TO COMPUTE PATH LENGTHS TO ALL CELLS FROM THE START CELL IN A 2D MAZE.
	 */
	public void findPathLengths(){
		pathLength[maze2d.startLoc.getX()][maze2d.goalLoc.getY()]=0;
		isVisited2D[maze2d.startLoc.getX()][maze2d.startLoc.getY()]=true;
		
		//CREATE A QUEUE AND PUSH THE START CELL INTO IT
		Queue<Dimension> q= new ConcurrentLinkedQueue<Dimension>();
		q.offer(maze2d.startLoc);
		
		while(!q.isEmpty()){
			
			Dimension u=q.poll();
			int a=u.getX();
			int b=u.getY();
			isVisited2D[a][b]=true;
			
			//FIND VALID MOVES FROM THE CURRENT CELL AND PUSH THEM INTO THE PRIORITY QUEUE.
			if(a-1>=0 && maze2d.maze[a-1][b]==maze2d.VALID_CELL && !isVisited2D[a-1][b]){
				q.offer(new Dimension(a-1,b));
				pathLength[a-1][b]=pathLength[a][b]+1;
			}
			if(a+1<maze2d.n && maze2d.maze[a+1][b]==maze2d.VALID_CELL && !isVisited2D[a+1][b]){
				q.offer(new Dimension(a+1,b));
				pathLength[a+1][b]=pathLength[a][b]+1;
			}
			if(b-1>=0 && maze2d.maze[a][b-1]==maze2d.VALID_CELL && !isVisited2D[a][b-1]){
				q.offer(new Dimension(a,b-1));
				pathLength[a][b-1]=pathLength[a][b]+1;
			}
			if(b+1<maze2d.n && maze2d.maze[a][b+1]==maze2d.VALID_CELL && !isVisited2D[a][b+1]){
				q.offer(new Dimension(a,b+1));
				pathLength[a][b+1]=pathLength[a][b]+1;
			}
			
		}
		for(int i=0;i<maze2d.n;i++){
			for(int j=0;j<maze2d.n;j++){
				if(!isVisited2D[i][j]){
					pathLength[i][j]=-1;
				}
			}
		}
	}
	

}
